// 题目链接：https://www.luogu.com.cn/problem/P1255

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 5005;

// 由于5000阶楼梯的走法数超过了long long表示的最大范围，因此采用一个二维数组来存储走法数的每一位
// f[i]这一行就表示了第i阶楼梯的走法总数，采用了逆序存储，因此输出是也要逆序输出
int f[N][N];

int len = 1; // 走法总数的位数

int main()
{
    int n;
    scanf("%d", &n);

    f[1][1] = 1, f[2][1] = 2; // 第一阶楼梯和第二阶楼梯分别只有1种和2种走法，只需存储在f[1][1],f[2][1]
    for (int i = 3; i <= n; ++i)
    {
        // 第i阶楼梯的走法数的每一位都等于第i-1和i-2阶楼梯的走法数的对应每一位相加
        for (int j = 1; j <= len; ++j)
        {
            f[i][j] = f[i - 1][j] + f[i - 2][j];
        }

        // 加完之后处理进位
        for (int j = 1; j <= len; ++j)
        {
            if (f[i][j] >= 10)
            {
                f[i][j + 1] += (f[i][j] / 10);
                f[i][j] %= 10;
            }
        }

        // 走法数的位数加1
        if (f[i][len + 1])
            ++len;
    }

    // 逆序输出
    for (int i = len; i >= 1; --i)
    {
        printf("%d", f[n][i]);
    }
    return 0;
}